To solve the low accuracy and high complexity in feature extraction of stereoscopic vision depth map, a feature extraction algorithm based on Principal Component Analysis and Histogram of Oriented Depth Gradient (PCA-HODG) was proposed. Firstly, disparity computation and depth map extraction were executed for binocular stereoscopic vision image to obtain high quality depth map; secondly, edge detection and gradient calculation of depth map within fixed size window were performed, then the features of region shape histograms were acquired and quantified. Meanwhile, dimensionality reduction by Principal Component Analysis (PCA) was implemented; finally, to realize the accuracy and completeness of feature extraction from depth map, a detection method of sliding window was used for the feature extraction of whole depth map and the dimensionality reduction was implemented once again. In the experiment of feature matching and classification, for the frames of test sequence Street, the average classification accuracy rate of the proposed algorithm increased by 1.15% when compared with the Range-Sample Depth Feature (RSDF) algorithm; while for Tanks, Tunnel, Temple, the average classification accuracy rate increased by 0.69%, 1.95%, 0.49% respectively when compared with the Geodesic Invariant Feature (GIF) algorithm. At the same time, the average running time decreased by 71.65%, 78.05%, 80.06% respectively compared with the Histogram of Oriented Depth (HOD), RSDF, GIF algorithm. The experimental results show that the proposed algorithm can not only detect and extract features of depth map more accurately, but also reduce the running time greatly by dimensionality reduction. Moreover, the proposed algorithm also has better robustness.